Many enterprises, and particularly Internet-based businesses, demand vast storage to store petabytes of large, binary objects that are referred to as “blobs.” Examples of such businesses include photo and video sharing Internet sites, e-auction sites, social networking sites, etc., for which information may be stored in geographically distributed storage nodes or data centers. Customers of these businesses need access to the stored information around the clock from locations around the globe. To perform satisfactorily for their customers, these types of businesses generally require reliable storage of the objects indefinitely into the future; quick retrieval of the objects at any time from any place in response to customer requests even in the face of data center outage and network partitions; and seamless scalability of storage capacity as the business expands. Oftentimes, these businesses use storage systems referred to as key-value stores to store the numerous binary large objects, where the value represents the blob to be stored in the system and the key provides an identifier that is associated with the value.